from data_structures.Queue import Queue
class bi_tree():
    class _tree_node():
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None
        self.count = 0

    def insert(self, value):
        new_node = self._tree_node(value)
        if self.count == 0:
            self.root = new_node
            self.count += 1
            return True
        #完全二叉树造树#层序遍历#广度优先
        #最坏时间复杂度On，优化，维护最后一个节点的指针
        q = Queue()
        q.enqueue_tail(self.root)
        while not q.is_empty:
            size = q.length()
            while size > 0:
                cur_node = q.dequeue_front()
                if cur_node.left is not None:
                    q.enqueue_tail(cur_node.left)
                    if cur_node.right is not None:
                        q.enqueue_tail(cur_node.right)
                    else:
                        cur_node.right = new_node
                        self.count+=1
                        return True
                else:
                    cur_node.left = new_node
                    self.count += 1
                    return True
                size -= 1
    
        
    def pre_order(self, node=None):
        """
        先序遍历
        """
        if node is None:
            return 
        
        print(node.value)
        self.pre_order(node.left)
        self.pre_order(node.right)
        
    def in_order(self, node=None):
        """
        中序遍历
        """
        if node is None:
            return 
        
        self.pre_order(node.left)
        print(node.value)
        self.pre_order(node.right)

    def last_order(self, node=None):
        """
        后序遍历
        """
        if node is None:
            return 
        
        self.pre_order(node.left)
        self.pre_order(node.right)
        print(node.value)

    def maxDepth(self):
        """
        层序遍历找最大深度
        """
        if self.root is None:
            return 0
        
        depth = 0
        q = Queue()
        q.enqueue_tail(self.root)
        while not q.is_empty:
            size = q.length()
            while size > 0:
                cur_node = q.dequeue_front()
                if cur_node.left is not None:
                    q.enqueue_tail(cur_node.left)
                if cur_node.right is not None:
                    q.enqueue_tail(cur_node.right)
                size -= 1
            depth += 1

        return depth